package 链表;

import java.util.ArrayList;
import java.util.List;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/8/6 9:09
 */
public class lc24两两交换链表中节点 {

    /*
     每k个一组 反转链表 k = 2
     */
    public ListNode solve(ListNode head, int k) {
        ListNode sentinel = new ListNode(-1), p0 = sentinel, cur = head;
        sentinel.next = head;
        int num = 0;
        while (cur != null) {
            num++;
            cur = cur.next;
        }

        ListNode pre = null, temp = null, nxt = null;
        cur = head;
        while (num >= k) {
            num -= k;
            for (int i = 0; i < k; i++) {
                temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }
            nxt = p0.next;
            p0.next.next = cur;
            p0.next = pre;
            p0 = nxt;
        }
        return sentinel.next;
    }




    /*
     添加哨兵的解法
     */

    public ListNode solution(ListNode head) {
        ListNode sentinel = new ListNode(-1), node0, node1;
        sentinel.next = head;
        node0 = sentinel;
        node1 = head;

        while (node1 != null && node1.next != null) {
            ListNode node2 = node1.next, node3 = node2.next;


            node0.next = node2;
            node2.next = node1;
            node1.next = node3;

//            node0 = node2;
            node0 = node1; // 最后 node0  是指向 node1 的 这点 有点绕, 注意一下!
            node1 = node3; //   而且 代码的顺序是不能变的

        }
        return sentinel.next;
    }


    /*
     递归写法:
      还是那句话, 时刻 去理解 递归函数的定义: f(node)  表示的 是 node--->node0----->x  node 和 node1交换成功, 然后递归到 f(x)
      f(x) 的含义: 表示的是, x--->x0 两两一组交换成功!
     */

    public ListNode recursion(ListNode node) {
        if (node == null || node.next == null) {
            return node;
        }
        ListNode node0 = node.next, node1 = node0.next;

        node.next = recursion(node1);
        node0.next = node;
        return node0;
    }


    /*
     思路不对, 是 相邻的两个 节点, 两两 一对交换,
     下面的实现是错误的!
     */
    public ListNode solve(ListNode head) {

        List<ListNode> list = new ArrayList<>();

        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur;
            list.add(cur);
            cur = cur.next;
            temp.next = null;
        }

        for (int i = 0; i < list.size() - 1; i++) {
            ListNode temp = list.get(i);
            list.set(i, list.get(i + 1));
            list.set(i + 1, temp);
        }
        ListNode sentinel = new ListNode(-1);
        head = sentinel;
        for (int i = 0; i < list.size(); i++) {
            head.next = list.get(i);
            head = head.next;
        }
        return sentinel.next;
    }


    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }


}
